package com.ward.bst;

import java.util.Stack;

/**
 * Created by ward on 2017-09-14.
 */
public class AVLTree {
    public class Node {
        private Integer balanceFactor;//平衡因子只能取-1，0，1
        private Integer value;
        private Node leftNode;
        private Node rightNode;
        private Node parentNode;

        public Integer getBalanceFactor() {
            return balanceFactor;
        }

        public void setBalanceFactor(Integer balanceFactor) {
            this.balanceFactor = balanceFactor;
        }

        public Integer getValue() {
            return value;
        }

        public void setValue(Integer value) {
            this.value = value;
        }

        public Node getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(Node leftNode) {
            this.leftNode = leftNode;
        }

        public Node getRightNode() {
            return rightNode;
        }

        public void setRightNode(Node rightNode) {
            this.rightNode = rightNode;
        }

        public Node getParentNode() {
            return parentNode;
        }

        public void setParentNode(Node parentNode) {
            this.parentNode = parentNode;
        }


        public Node(Integer value, Integer balanceFactor, Node leftNode, Node rightNode, Node parentNode) {
            super();
            this.balanceFactor = balanceFactor;
            this.value = value;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
            this.parentNode = parentNode;
        }
    }

    private Node rootNode;

    public Node getRootNode() {
        return rootNode;
    }

    public void setRootNode(Node rootNode) {
        this.rootNode = rootNode;
    }


    /**
     * @param currentNode 当前节点
     * @desc 获得当前节点的兄弟节点
     */
    private Node getBrotherNode(Node currentNode) {
        Node parentNode = currentNode.getParentNode();
        if (null == parentNode) {
            return null;
        }
        Node brotherNode = (currentNode == parentNode.getLeftNode()) ? parentNode.getRightNode() : parentNode.getLeftNode();
        return brotherNode;
    }

    private void leftRotate(Node currentNode) {
        //当前节点的右孩子
        Node rightChild = currentNode.getRightNode();
        if (null == rightChild) {
            return;
        }
        //当前节点右孩子的左孩子
        Node rLChildNode = rightChild.getLeftNode();


        //当前节点的父节点
        Node parent = currentNode.getParentNode();


        //变更1
        if (null == parent) { //若当前节点 根节点 则会出现为null的情况
            this.setRootNode(rightChild);
            //??? 根节点 不存在 父节点
            rightChild.setParentNode(null);

        } else {
            if (parent.getRightNode() == (currentNode)) {
                parent.setRightNode(rightChild);
            } else {
                parent.setLeftNode(rightChild);
            }
            rightChild.setParentNode(parent);
        }


        //变更2
        rightChild.setLeftNode(currentNode);
        currentNode.setParentNode(rightChild);

        //变更3

        if (null != rLChildNode) {
            rLChildNode.setParentNode(currentNode);
        } else {
            //如果rLChildNode 为NULL 的情况 怎么处理？？
        }
        currentNode.setRightNode(rLChildNode);

        return;
    }

    private void rightRotate(Node currentNode) {
    /*
          parent              parent
            |                   |
            A                   B
           / \                 / \
          B   C    ----->     D   A
         / \                     / \
        D   E                   E   C
        */
        //当前节点的父节点
        Node parent = currentNode.getParentNode();
        //当前节点的左孩子
        Node leftChild = currentNode.getLeftNode();
        if (null == leftChild) {
            //如果为null 则无法进行 右旋转 操作
            return;
        }
        Node lRChild = leftChild.getRightNode(); //当前节点的左孩子的右孩子
        //变更1
        if (null == parent) {
            this.setRootNode(leftChild);
            // ??? 根节点  不存在  父节点
            leftChild.setParentNode(null);
        } else {
            if (parent.getLeftNode() == (currentNode)) {
                //旋转的中心节点  是其父节点的 左孩子
                parent.setLeftNode(leftChild);
            } else {
                //旋转的中心节点  是其父节点的 右孩子
                parent.setRightNode(leftChild);
            }
            leftChild.setParentNode(parent);
        }

        //变更2
        currentNode.setParentNode(leftChild);
        leftChild.setRightNode(currentNode);

        //变更3

        if (null != lRChild) {
            lRChild.setParentNode(currentNode);
            //
        }
        // currentNode.setRightNode(cLRChild);
        currentNode.setLeftNode(lRChild);

    }

    private Node findInsertParentNode(Integer value) {
        Node currentNode = rootNode;
        Node preCurrentNode = rootNode;
        while (null != currentNode) {
            if (value > currentNode.getValue()) {
                preCurrentNode = currentNode;
                currentNode = currentNode.getRightNode();
            } else {
                preCurrentNode = currentNode;
                currentNode = currentNode.getLeftNode();
            }
        }

        return preCurrentNode;
    }

    public void insertValue(Integer value) {
        Node insertNode = new Node(value, 0, null, null, null);
        Node insertParentNode = this.findInsertParentNode(value);
        if (null != insertParentNode) {
            if (value > insertParentNode.getValue()) {
                insertParentNode.setRightNode(insertNode);
            } else {
                insertParentNode.setLeftNode(insertNode);
            }
        }
        insertNode.setParentNode(insertParentNode);
        this.insertNodeFix(insertNode);
    }

    /**
     * @param currentNode
     * @desc 左子树+1  右子树-1
     */
    private void insertNodeFix(Node currentNode) {
        Node parentNode = currentNode.getParentNode();
        if (null == parentNode) {
            this.setRootNode(currentNode);
            return;
        }
        Boolean currentLeftParent = (currentNode == parentNode.getLeftNode()) ? true : false;
        Node grandParentNode = parentNode.getParentNode();
        if (currentLeftParent) {
            parentNode.setBalanceFactor(parentNode.getBalanceFactor() + 1);
        } else {
            parentNode.setBalanceFactor(parentNode.getBalanceFactor() - 1);
        }
        if (null == grandParentNode || 0 == parentNode.getBalanceFactor()) {
            return;
        }
        Boolean parentLeftGrand = (parentNode == grandParentNode.getLeftNode()) ? true : false;
       /* if (0 == parentNode.getBalanceFactor()) {
            return;
        }*/
       /* if (parentLeftGrand) {
            grandParentNode.setBalanceFactor(grandParentNode.getBalanceFactor() + 1);
        } else {
            grandParentNode.setBalanceFactor(grandParentNode.getBalanceFactor() - 1);
        }
        if (0 == grandParentNode.getBalanceFactor()) {
            return;
        }*/

        //第一个字母表示 父节点相对于祖父节点是左L还是右R，第二个字母表示当前节点 相对于 父节点 是左L还是右R
        if (parentLeftGrand && currentLeftParent && 1 == grandParentNode.getBalanceFactor()) {//LL型
            grandParentNode.setBalanceFactor(grandParentNode.getBalanceFactor() - 1);
            parentNode.setBalanceFactor(parentNode.getBalanceFactor() - 1);
            this.rightRotate(grandParentNode);
        } else if (parentLeftGrand && !currentLeftParent && 1 == grandParentNode.getBalanceFactor()) {//LR型
            parentNode.setBalanceFactor(parentNode.getBalanceFactor() + 1);
            this.leftRotate(parentNode);
            grandParentNode.setBalanceFactor(grandParentNode.getBalanceFactor() - 1);
            this.rightRotate(grandParentNode);
        } else if (!parentLeftGrand && currentLeftParent && -1 == grandParentNode.getBalanceFactor()) {//RL型
            parentNode.setBalanceFactor(parentNode.getBalanceFactor() - 1);
            this.rightRotate(parentNode);
            grandParentNode.setBalanceFactor(grandParentNode.getBalanceFactor() + 1);
            this.leftRotate(grandParentNode);
        } else if (!parentLeftGrand && !currentLeftParent && -1 == grandParentNode.getBalanceFactor()) {//RR型
            grandParentNode.setBalanceFactor(grandParentNode.getBalanceFactor() + 1);
            parentNode.setBalanceFactor(parentNode.getBalanceFactor() + 1);
            this.leftRotate(grandParentNode);
        }
        if (0 != parentNode.getBalanceFactor()) {
            this.insertNodeFix(parentNode);
        }
        return;
    }


    private Node findDeleteNode(Integer value) {
        Node currentNode = rootNode;
        while (null != currentNode) {
            if (value > currentNode.getValue()) {
                currentNode = currentNode.getRightNode();
            } else if (value < currentNode.getValue()) {
                currentNode = currentNode.getLeftNode();
            } else {
                return currentNode;
            }
        }
        return null;
    }


    /**
     * @param currentNode
     * @desc 查询二叉树中 某个节点的 前驱节点
     */
    private Node findPrecursorNode(Node currentNode) {
        Node tempNode = currentNode.getLeftNode();
        if (null == tempNode) {
            return null;
        }
        while (null != tempNode.getRightNode()) {
            tempNode = tempNode.getRightNode();
        }
        return tempNode;
    }

    private void exchangeValue(Node delNode, Node preNode) {
        Integer temp = delNode.getValue();
        delNode.setValue(preNode.getValue());
        preNode.setValue(temp);
    }

    /**
     * @param parentNode  实际删除节点的父节点
     * @param brotherNode 实际删除节点的兄弟节点
     */
    private void deleteNodeFix(Node parentNode, Node brotherNode) {
        if (null == parentNode) {
            return;
        }
        Boolean brotherLeftParent = (brotherNode == parentNode.getLeftNode()) ? true : false;
        Boolean currentLeftParent = !brotherLeftParent;
      /*  if(null==parentNode.getParentNode()){//此处判断 父节点是否为root节点
            if(currentLeftParent){
                parentNode.setBalanceFactor(parentNode.getBalanceFactor()-1);
            }else {
                parentNode.setBalanceFactor(parentNode.getBalanceFactor()+1);
            }
            return;
        }*/

        Node leftNephewNode, rightNephewNode;
        if (null == brotherNode) {
            // return;
            Node currentNode = parentNode;
            if (currentLeftParent) {
                parentNode.setBalanceFactor(parentNode.getBalanceFactor() - 1);
            } else {
                parentNode.setBalanceFactor(parentNode.getBalanceFactor() + 1);
            }
            this.deleteNodeFix(currentNode.getParentNode(), getBrotherNode(currentNode));
            return;
        } else {
            leftNephewNode = brotherNode.getLeftNode();
            rightNephewNode = brotherNode.getRightNode();
        }

        if (null == leftNephewNode && null == rightNephewNode) {
            if (brotherLeftParent) {
                parentNode.setBalanceFactor(parentNode.getBalanceFactor() + 1);
            } else {
                parentNode.setBalanceFactor(parentNode.getBalanceFactor() - 1);
            }
            return;
        }

        //
        Node currentNode = null;
        if (brotherLeftParent) {
            if (null != leftNephewNode && null != rightNephewNode && 1 == parentNode.getBalanceFactor()) {
                //LL 型-----两个侄子均存在
                //parentNode.setBalanceFactor(1); 改成下面

                brotherNode.setBalanceFactor(brotherNode.getBalanceFactor() - 1);
                if(null!=parentNode.getRightNode()){//???????  后续递归调用不会真的删除
                    parentNode.setBalanceFactor(parentNode.getBalanceFactor() - 1);
                }

                this.rightRotate(parentNode);
                currentNode = brotherNode;
            } else if (null != leftNephewNode && null == rightNephewNode && 1 == parentNode.getBalanceFactor()) {
                //LL 型----只存在左侄子
                //parentNode.setBalanceFactor(0); 改成下面

                brotherNode.setBalanceFactor(brotherNode.getBalanceFactor() - 1);
                parentNode.setBalanceFactor(parentNode.getBalanceFactor() - 1);
                this.rightRotate(parentNode);
                currentNode = brotherNode;
            } else if (null == leftNephewNode && null != rightNephewNode && 1 == parentNode.getBalanceFactor()) {
                //LR 型-----只存在右侄子
                brotherNode.setBalanceFactor(brotherNode.getBalanceFactor() + 1);
                parentNode.setBalanceFactor(parentNode.getBalanceFactor() - 1);
                this.leftRotate(brotherNode);
                this.rightRotate(parentNode);
                currentNode = leftNephewNode;
            }
        } else {
            if (null != leftNephewNode && null != rightNephewNode && -1 == parentNode.getBalanceFactor()) {
                //RR型  ----两侄子均存在
                // parentNode.setBalanceFactor(-1); 改成下面的


                brotherNode.setBalanceFactor(brotherNode.getBalanceFactor() + 1);
                if(null!=parentNode.getLeftNode()){//???????  后续递归调用不会真的删除
                    parentNode.setBalanceFactor(parentNode.getBalanceFactor() + 1);
                }

                this.leftRotate(parentNode);
                currentNode = brotherNode;
            } else if (null == leftNephewNode && null != rightNephewNode && -1 == parentNode.getBalanceFactor()) {
                //RR型 -----只存在右侄子
                //parentNode.setBalanceFactor(0);  改成下面的

                brotherNode.setBalanceFactor(brotherNode.getBalanceFactor() + 1);
                parentNode.setBalanceFactor(parentNode.getBalanceFactor() + 1);
                this.leftRotate(parentNode);
                currentNode = brotherNode;
            } else if (null != leftNephewNode && null == rightNephewNode && -1 == parentNode.getBalanceFactor()) {
                //RL型----只存在左侄子

                brotherNode.setBalanceFactor(brotherNode.getBalanceFactor() - 1);
                parentNode.setBalanceFactor(parentNode.getBalanceFactor() + 1);
                this.rightRotate(brotherNode);
                this.leftRotate(parentNode);
                currentNode = leftNephewNode;
            }
        }

        if (0 == currentNode.getBalanceFactor()) {//注意！！！！！ 为啥是等于0？？ 需要论证
            this.deleteNodeFix(currentNode.getParentNode(), getBrotherNode(currentNode));
        }
        return;

    }


    private void deleteNodeFixNew(Node parentNode,Node brotherNode){
        if(null==brotherNode){//兄弟节点为null
            if(null==parentNode){
                return;
            }else{
                parentNode.setBalanceFactor(0);//此处 父节点的平衡因子 一定为0
                Node currentNode = parentNode;
                this.deleteNodeFixNew(currentNode.getParentNode(), getBrotherNode(currentNode));
                return;
            }
        }else{
            //如果兄弟节点不为null  则父节点 一定存在 (即不为null)
            Boolean brotherLeftParent = (brotherNode == parentNode.getLeftNode()) ? true : false;
            Boolean currentLeftParent = !brotherLeftParent;
            Node leftNephewNode = brotherNode.getLeftNode();
            Node rightNephewNode = brotherNode.getRightNode();

            Node currentNode = null;
            if (brotherLeftParent) {//此处为啥要判断 兄弟节点是在 父节点的 左 还是右？？
                if(1==parentNode.getBalanceFactor()){//当父节点的平衡因子 为 1时，一定不会出现  左、右 侄子为null的情况
                    if (null != leftNephewNode && null != rightNephewNode ) {
                        //LL 型-----两个侄子均存在
                        brotherNode.setBalanceFactor(brotherNode.getBalanceFactor() - 1);
                        if(null!=parentNode.getRightNode()){//???????  后续递归调用不会真的删除
                            parentNode.setBalanceFactor(parentNode.getBalanceFactor() - 1);
                        }
                        this.rightRotate(parentNode);
                        currentNode = brotherNode;
                    } else if (null != leftNephewNode && null == rightNephewNode ) {
                        //LL 型----只存在左侄子
                        brotherNode.setBalanceFactor(brotherNode.getBalanceFactor() - 1);
                        parentNode.setBalanceFactor(parentNode.getBalanceFactor() - 1);
                        this.rightRotate(parentNode);
                        currentNode = brotherNode;
                    } else if (null == leftNephewNode && null != rightNephewNode ) {
                        //LR 型-----只存在右侄子
                        brotherNode.setBalanceFactor(brotherNode.getBalanceFactor() + 1);
                        parentNode.setBalanceFactor(parentNode.getBalanceFactor() - 1);
                        this.leftRotate(brotherNode);
                        this.rightRotate(parentNode);
                        currentNode = leftNephewNode;
                    }
                }else{//当父节点的平衡因子 为 -1、0时，一定不
                    parentNode.setBalanceFactor(parentNode.getBalanceFactor()+1);
                    currentNode=parentNode;
                }
            }else {
                    if(-1==parentNode.getBalanceFactor()){//当父节点的平衡因子 为 -1时，一定不会出现  左、右 侄子为null的情况
                        if (null != leftNephewNode && null != rightNephewNode ) {
                            //RR型  ----两侄子均存在
                            brotherNode.setBalanceFactor(brotherNode.getBalanceFactor() + 1);
                            if(null!=parentNode.getLeftNode()){//???????  后续递归调用不会真的删除
                                parentNode.setBalanceFactor(parentNode.getBalanceFactor() + 1);
                            }
                            this.leftRotate(parentNode);
                            currentNode = brotherNode;
                        } else if (null == leftNephewNode && null != rightNephewNode ) {
                            //RR型 -----只存在右侄子
                            brotherNode.setBalanceFactor(brotherNode.getBalanceFactor() + 1);
                            parentNode.setBalanceFactor(parentNode.getBalanceFactor() + 1);
                            this.leftRotate(parentNode);
                            currentNode = brotherNode;

                        } else if (null != leftNephewNode && null == rightNephewNode ) {
                            //RL型----只存在左侄子
                            brotherNode.setBalanceFactor(brotherNode.getBalanceFactor() - 1);
                            parentNode.setBalanceFactor(parentNode.getBalanceFactor() + 1);
                            this.rightRotate(brotherNode);
                            this.leftRotate(parentNode);
                            currentNode = leftNephewNode;
                        }
                    }else{
                        parentNode.setBalanceFactor(parentNode.getBalanceFactor()-1);
                        currentNode=parentNode;
                    }
            }
            //注意 此处的 currentNode 已经是经过上面 旋转调整后重新赋予的，而且每种类型的赋值是不一样的，
            //但是 有一点是可以确定的，他们都是旋转后 真正的父节点
            if(0==currentNode.getBalanceFactor()){
                this.deleteNodeFixNew(currentNode.getParentNode(), getBrotherNode(currentNode));
            }
            return;
        }

    }


    public void deleteNode(Integer value) {
        Node originDeleteNode = this.findDeleteNode(value);
        if (null == originDeleteNode) {
            System.out.println();
            System.out.println("要删除的值不存在" + value);
            return;
        }
        //实际删除的节点
        Node originDelLChild = originDeleteNode.getLeftNode();
        Node originDelRChild = originDeleteNode.getRightNode();
        Node currentNode, trueDelNodeLChild, trueDelNodeRChild;
        if (null != originDelLChild && null != originDelRChild) {
            //1.原始要删除的节点，有两个孩子节点
            //先找到前驱节点
            Node precursorNode = this.findPrecursorNode(originDeleteNode);
            //交换原始删除节点 和前驱节点的值
            this.exchangeValue(originDeleteNode, precursorNode);
            //实际被删除的节点为中心点，转化为 情况2.3.4 中的一种情况处理
            currentNode = precursorNode;
            trueDelNodeLChild = currentNode.getLeftNode();
            trueDelNodeRChild = currentNode.getRightNode();
            //！注意,后续将判断转化为 2.3.4 中的那种情况.......

        } else {
            //如果不符合 上述的情况，那么原始要删除的节点就是   真实删除的节点就是
            currentNode = originDeleteNode;
            trueDelNodeLChild = originDelLChild;
            trueDelNodeRChild = originDelRChild;
        }

        Node parentNode = currentNode.getParentNode();//实际要删除的节点的父节节点，有可能为null
        Node brotherNode = this.getBrotherNode(currentNode);//实际要删除的节点的兄弟节点,有可能为null
        if (null != trueDelNodeLChild && null == trueDelNodeRChild) {
            //   2.真实要删除的节点仅有一个左孩子
            if (null == parentNode) {//如果父节点为null，则说明真实删除的节点为root节点
                this.setRootNode(trueDelNodeLChild);
                trueDelNodeLChild.setParentNode(null);
            } else {
                Boolean currentLeftParent = (currentNode == parentNode.getLeftNode()) ? true : false;
                currentNode.setParentNode(null);
                if (currentLeftParent) {
                    parentNode.setLeftNode(trueDelNodeLChild);
                } else {
                    parentNode.setRightNode(trueDelNodeLChild);
                }
                trueDelNodeLChild.setParentNode(parentNode);
            }
            this.deleteNodeFixNew(parentNode, brotherNode);

        } else if (null == trueDelNodeLChild && null != trueDelNodeRChild) {
            //3.真实要删除的节点仅有一个右孩子
            if (null == parentNode) {//如果父节点为null，则说明真实删除的节点为root节点
                this.setRootNode(trueDelNodeRChild);
                trueDelNodeRChild.setParentNode(null);
            } else {
                Boolean currentLeftParent = (currentNode == parentNode.getLeftNode()) ? true : false;
                currentNode.setParentNode(null);
                if (currentLeftParent) {
                    parentNode.setLeftNode(trueDelNodeRChild);
                } else {
                    parentNode.setRightNode(trueDelNodeRChild);
                }
                trueDelNodeRChild.setParentNode(parentNode);
            }
            this.deleteNodeFixNew(parentNode, brotherNode);

        } else if (null == trueDelNodeLChild && null == trueDelNodeRChild) {
            //4.真实要删除的节点没有孩子节点
            if (null == parentNode) {//如果父节点为null，则说明真实删除的节点为root节点
                this.setRootNode(null);
            } else {
                Boolean currentLeftParent = (currentNode == parentNode.getLeftNode()) ? true : false;
                currentNode.setParentNode(null);
                if (currentLeftParent) {
                    parentNode.setLeftNode(null);
                } else {
                    parentNode.setRightNode(null);
                }
            }
            this.deleteNodeFixNew(parentNode, brotherNode);

        }
        return;
    }


    /**
     * @param rootNode
     * @desc 中序遍历  左根右  ---非递归实现
     */
    public void inorderTraversal(Node rootNode) {
        Stack<Node> nodeStack = new Stack<>();
        Node tempNode = rootNode;
        while (null != tempNode || !nodeStack.isEmpty()) {
            while (null != tempNode) {
                nodeStack.push(tempNode);
                tempNode = tempNode.getLeftNode();
            }
            if (!nodeStack.isEmpty()) {
               /* tempNode=nodeStack.peek();//查看堆栈顶部的对象，但不从堆栈中移除它。
                System.out.print(tempNode.getValue()+",");
                nodeStack.pop();//移除堆栈顶部的对象，并作为此函数的值返回该对象。*/
                tempNode = nodeStack.pop();//移除堆栈顶部的对象，并作为此函数的值返回该对象。
                System.out.print(tempNode.getValue() + ",");
                tempNode = tempNode.getRightNode();
            }
        }
        return;

    }

    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();

        Integer[] valueArr = {9, 19, 8, 20, 28, 4545, 88, 98,/* 25, 456, 7, 6, 5, 4*/};
        for (int i = 0; i < valueArr.length; i++) {
            System.out.println("AVL树开始插入" + valueArr[i]);
            avlTree.insertValue(valueArr[i]);
            System.out.println("AVL树插入结束" + valueArr[i]);
        }
        System.out.println();
        System.out.println("---------------------------");
        avlTree.inorderTraversal(avlTree.getRootNode());
        System.out.println();
        avlTree.deleteNode(8);
        System.out.println("---------------------------");
        avlTree.inorderTraversal(avlTree.getRootNode());
        System.out.println();
        avlTree.deleteNode(19);
        System.out.println("---------------------------");
        avlTree.inorderTraversal(avlTree.getRootNode());

    }
}
